home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_400 / 422_02 / misc / hanoi.c < prev    next >
C/C++ Source or Header  |  1994-03-20  |  4KB  |  180 lines
  1. /*
  2.  * Towers of Hanoi
  3.  *
  4.  * This program solves the "Towers of Hanoi" problem, which is to move a stack
  5.  * of different sized rings from one of three towers to another. Only one ring
  6.  * may be moved at a time, and a ring may not be placed on top of a smaller
  7.  * ring.
  8.  *
  9.  * Original Author Unknown
  10.  *
  11.  * Compile command: cc hanoi -fop
  12.  */
  13. #include <stdio.h>            /* Standard I/O definitions */
  14. #include <video.h>            /* Video    I/O definitions */
  15.  
  16. #define POST            0xB3
  17. #define POST_BASE        0xC1
  18. #define BASE            0xC4
  19. #define RING            0xDC
  20.  
  21. #define SCREEN_WIDTH    80
  22. #define SCREEN_HEIGHT    25
  23.  
  24. #define RING_WIDTH        ((((SCREEN_WIDTH-2)/3)&0xFE)-1)
  25. #define LEFT_POST        (RING_WIDTH/2+1)
  26. #define CENTER_POST        (LEFT_POST+RING_WIDTH)
  27. #define RIGHT_POST        (LEFT_POST+2*RING_WIDTH)
  28.  
  29. #define MOVING_ROW        2
  30. #define BASE_ROW        15
  31. #define POST_HEIGHT        11
  32.  
  33.     char top[3] = { BASE_ROW-1, BASE_ROW-1, BASE_ROW-1 };
  34.     unsigned pause;
  35.  
  36. /*
  37.  * Main program, draw the posts & begin moving rings
  38.  */
  39. main(argc, argv)
  40.     int argc;
  41.     char *argv[];
  42. {
  43.     int nrings, i;
  44.  
  45.     if(argc < 2  ||  argc > 3)
  46.         abort("\nUse: hanoi <rings> [delay]\n");
  47.  
  48.     nrings = atoi(argv[1]);                        /* Number of rings */
  49.     pause = argc > 2 ? atoi(argv[2]) : 2500;    /* Delay count */
  50.  
  51.     vopen();
  52.  
  53.     /* Draw the posts */
  54.     for(i = MOVING_ROW+2; i < BASE_ROW; ++i) {
  55.         putxy(LEFT_POST, i, POST);
  56.         putxy(CENTER_POST, i, POST);
  57.         putxy(RIGHT_POST, i, POST); }
  58.  
  59.     /* Draw the base */
  60.     vgotoxy(0, BASE_ROW);
  61.     for(i = 1; i < SCREEN_WIDTH; ++i)
  62.         vputc(BASE);
  63.  
  64.     /* Draw the post-base connections */
  65.     putxy(LEFT_POST, BASE_ROW, POST_BASE);
  66.     putxy(CENTER_POST, BASE_ROW, POST_BASE);
  67.     putxy(RIGHT_POST, BASE_ROW, POST_BASE);
  68.  
  69.     /* Draw the title */
  70.     vgotoxy(30, BASE_ROW+2);
  71.     V_ATTR = REVERSE;
  72.     vputs(" TOWERS OF HANOI ");
  73.     V_ATTR = NORMAL;
  74.  
  75.     /* Draw the initial ring positions */
  76.     for(i = nrings; i > 0; --i)
  77.         draw(i, LEFT_POST, top[0]--, RING);
  78.  
  79.     /* Perform the movements */
  80.     hanoi(nrings, 0, 2, 1);
  81.     vgotoxy(0, 20);
  82. }
  83.  
  84. /*
  85.  * Performs towers of hanoi movements by recursing from the current
  86.  * position to the bottom of the ring stack, moving a single ring,
  87.  * and walking back up again, re-arranging the movements with each
  88.  * recursion.
  89.  */
  90. hanoi(n, a, b, c)
  91.     char n, a, b, c;
  92. {
  93.     if(n) {
  94.         hanoi(n-1, a, c, b);
  95.         movering(n, a, b);
  96.         hanoi(n-1, c, b, a); }
  97. }
  98.  
  99. /*
  100.  * Place a character on the screen at a specified X/Y address
  101.  */
  102. putxy(x, y, c)
  103.     char c;
  104.     int x,y;
  105. {
  106.     vgotoxy(x,y);
  107.     vputc(c);
  108. }
  109.  
  110. /*
  111.  * Draw a ring at a position on the screen
  112.  */
  113. draw(ring, centre, y, c)
  114.     char ring, centre, y, c;
  115. {
  116.     char i;
  117.  
  118.     vgotoxy(centre-ring, y);
  119.  
  120.     for(i=0; i<ring; ++i)
  121.         vputc(c);
  122.  
  123.     vgotoxy(centre+1, y);
  124.  
  125.     for(i=0; i<ring; ++i)
  126.         vputc(c);
  127. }
  128.  
  129. /*
  130.  * Move a ring between two posts by repeatedly drawing and erasing it
  131.  */
  132. movering(ring, from, to)
  133.     char ring, from, to;
  134. {
  135.     char fromc, toc;
  136.     char fromy, toy;
  137.  
  138.     fromc = LEFT_POST + from * RING_WIDTH;
  139.     toc = LEFT_POST + to * RING_WIDTH;
  140.     fromy = ++top[from];
  141.     toy = top[to]--;
  142.  
  143.     while(fromy != MOVING_ROW) {
  144.         draw(ring, fromc, fromy, ' ');
  145.         draw(ring, fromc, --fromy, RING);
  146.         wait(); }
  147.  
  148.     if(fromc < toc)
  149.         while(fromc != toc) {
  150.             putxy(fromc-ring, fromy, ' ');
  151.             putxy(fromc, fromy, RING);
  152.             putxy(fromc+1, fromy, ' ');
  153.             putxy(fromc+ring+1, fromy, RING);
  154.             ++fromc;
  155.             wait(); }
  156.     else if (fromc > toc)
  157.         while(fromc != toc) {
  158.             putxy(fromc+ring, fromy, ' ');
  159.             putxy(fromc, fromy, RING);
  160.             putxy(fromc-1, fromy, ' ');
  161.             putxy(fromc-ring-1, fromy, RING);
  162.             --fromc;
  163.             wait(); }
  164.  
  165.     while(fromy != toy) {
  166.         draw(ring, fromc, fromy, ' ');
  167.         draw(ring, fromc, ++fromy, RING);
  168.         wait(); }
  169. }
  170.  
  171. /*
  172.  * Wait a pre-defined delay period
  173.  */
  174. wait()
  175. {
  176.     int i;
  177.  
  178.     for(i=0; i < pause; ++i);
  179. }
  180.